\documentclass{beamer}

\usepackage{beamerthemesplit}
\setbeamertemplate{navigation symbols}{} % Get rid of stupid nav symbols

\title{Linux Fair-share Group Scheduling Lab}
\author{Charlie Moore \and Aaron Lovato \and Juston Moore \and William Vu}
\date{March 24, 2010}
\institute[NMT]{New Mexico Tech}

\begin{document}
\section{Introduction}
\frame{\titlepage}
\frame{\tableofcontents}

\begin{frame}{Scheduling in Linux}
\begin{itemize}
    \item Two basic schedulers, each with multiple policies.
    \begin{itemize}
        \item Real-time scheduler.
        \item Completely fair scheduler (CFS).
    \end{itemize}
    \item The objectives:
      \begin{itemize}
        \item Learn how scheduling is implemented in Linux
        \item Implement a fair-share group scheduling policy without
        disrupting existing scheduling policies.
      \item Create a system call to report the time used by a given group.
    \end{itemize}
\end{itemize}
\end{frame}

\section{Design}
\begin{frame}{Design Options}
\begin{itemize}
    \item Entirely new scheduler.
    \begin{itemize}
        \item Too much to write and test.
        \item Integration with existing schedulers could be complicated.
    \end{itemize}
    \item Use existing scheduler.
    \begin{itemize}
        \item Use the CFS.
        \begin{itemize}
            \item Actually implements fair group scheduling already.
            \item Complicated implementation.
            \item Non-strict time slicing.
        \end{itemize}
        \item Use the real-time scheduler.
        \begin{itemize}
            \item Predictably chooses next task.
            \item Simpler implementation than the CFS.
            \item Supports round-robin scheduling.
        \end{itemize}
    \end{itemize}
\end{itemize}

\end{frame}

\begin{frame}{Basic Design}
  \begin{itemize}
  \item Defined a configurable (at kernel compile time) number of groups. The
    group number is specified by a parameter in the structure passed to the
    \texttt{sched\_setscheduler()} function.
  \item Tasks in the FSG scheduling policy are run in the real-time
    scheduler with priority 1.
  \item Task time slices are altered to allot equal run times to each task group,
    with each task inside of the group getting an equal relative time slice from
    the group's time slice.
  \end{itemize}
\end{frame}

\begin{frame}{Design Details}
\begin{itemize}
    \item Define the \texttt{SCHED\_FSG} scheduling policy.
    \item Modify \texttt{sched\_setscheduler()} to handle \texttt{SCHED\_FSG}
    tasks.
    \item Make \texttt{SCHED\_FSG} a real-time policy.
    \item Use an approach similar to \texttt{SCHED\_RR} to implement
    time slicing.
    \item Keep track of \texttt{SCHED\_FSG} tasks along with their related 
    information in a linked list.
    \begin{itemize}
        \item Update this list when tasks are added/removed from a group.
        \item Recalculate time slices when this list is modified.
    \end{itemize}
    \item Update time count for a group on each tick.
\end{itemize}
\end{frame}


\section{Implementation}
\begin{frame}[fragile] \frametitle{Two New Challengers Appear!}
\begin{verbatim}
struct fsg_task_list {
  struct list_head list; // Make into a linked list node
  struct task_struct *task; // The task we're representin'
};

struct fsg_group {
  struct fsg_task_list tasks; // List of tasks
  int size; // Number of tasks in this group
  time_t total_time; // Total time used by all tasks
  // Change time slices when we gain/lose tasks
  void (*recalculate_timeslices) (struct task_struct *);
};
\end{verbatim}
\end{frame}

\begin{frame}[fragile] \frametitle{Existing Data Structure Diffs}
\begin{verbatim}
struct task_struct {
+  struct fsg_group *fsgroup;
...
};

struct rt_rq {
+  // To keep track of tasks in each group
+  struct fsg_group groups[FSG_MAX_GROUPS];
...
};
\end{verbatim}
\end{frame}

\begin{frame}[fragile] \frametitle{Existing Data Structure Diffs II}
\begin{verbatim}
struct sched_param {
  int sched_priority;
+  int sched_group; // Group to add the task to
};

struct sched_rt_entity {
...
+  // The time slice this entity should be allotted when
+  // it exhausts its current time slice.
+  unsigned int full_time_slice;
...
};
\end{verbatim}
\end{frame}

\begin{frame}[fragile] \frametitle{\texttt{sched\_setscheduler()}}
  \begin{itemize}
  \item Add our policy to the various sanity checks.
  \item If the task is already \texttt{SCHED\_FSG}, remove it from its current
    group before rescheduling.
  \item \texttt{kmalloc} us up a shiny new linked list node.
  \item Configure it and add it to the proper group's list.  Check out that
    indirection.
\begin{verbatim}
list_add_tail(&tmp_fsg_list->list,
    &(rq->rt.groups[param->sched_group].tasks.list));
\end{verbatim}
  \item Finally, we have to recalculate our time slices.
  \end{itemize}
\end{frame}

\begin{frame}[fragile] \frametitle{\texttt{do\_exit()}}
\begin{verbatim}
struct list_head *c, *n;
struct fsg_task_list *tmp;
list_for_each_safe(c, n, &(tsk->fsgroup->tasks.list)) {
  tmp = list_entry(c, struct fsg_task_list, list);
  if (tmp->task == tsk)
    list_del(c);
}
\end{verbatim}
We have to iterate like this because it's impossible to use the
\texttt{container\_of} macro in our case.  Long story short, we're storing a
pointer instead of the \texttt{task\_struct} itself.  Unfortunately this means
our delete algorithm is $O(n)$ where $n$ is the number of tasks in the group.
\end{frame}

\begin{frame}{Time Slicing}
  \begin{itemize}
    \item \texttt{GROUP\_TIMESLICE} = \texttt{DEFAULT\_TIMESLICE} *
      \texttt{num\_max\_procs}
    \item \texttt{PROCESS\_TIMESLICE} = \texttt{GROUP\_TIMESLICE} /
      \texttt{num\_procs\_in\_group}
    \item Groups run round-robin
    \item FSG tasks preempt normal tasks because they are scheduled as real-time
      processes
  \end{itemize}
\end{frame}

\section{Demo}
\begin{frame}{Details}
  \begin{itemize}
    \item The parent "monitor" process is scheduled as realtime priority 0 so that it
	  cannot be starved by child tasks.
    \item Parent process creates $2^i$ processes for group $i$, $0 <= i < 5$
    \item Children are scheduled in their respective group and run forever
    \item Parent incrementally invokes our syscall to check each group's run time
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{center}
    \huge{DEMO}
  \end{center}
\end{frame}

\section{Conclusion}
\begin{frame}{Conclusion}
  \begin{itemize}
  \item System designed for throughput rather than response time, just like
    other real-time scheduling algorithms
  \item We implemented a fair-share group scheduler with equal time sharing
    among the groups and relatively equal time sharing within the groups.
  % lol at adverbing "round-robin"
  \item The scheduling of groups is performed round-robin, and scheduling
    of tasks within a group is also performed round-robin.
  \item We implemented a system call to return the \textbf{cumulative}
    run time of each task group.
  \end{itemize}
\end{frame}

\end{document}
